home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 1085 < prev    next >
Encoding:
Internet Message Format  |  1996-08-06  |  1.0 KB
  1. Path: news.bridge.net!news
  2. From: David Byrden <100101.2547@compuserve.com>
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: deque container - how to implement?
  5. Date: 9 Jan 1996 06:01:39 GMT
  6. Organization: self-employed
  7. Message-ID: <4ct0c3$9gg@news.bridge.net>
  8. References: <4ce651$92t@galaxy.uci.agh.edu.pl>
  9. NNTP-Posting-Host: ppp-mia1-58.bridge.net
  10. Mime-Version: 1.0
  11. Content-Type: text/plain; charset=us-ascii
  12. Content-Transfer-Encoding: 7bit
  13. X-Mailer: Mozilla 1.1N (Windows; I; 16bit)
  14.  
  15.  
  16. Jurek;
  17.  
  18. I have hardly studied deque and have never seen an implementation, but I 
  19. will bet that it works like this; it consists of a contigous block of 
  20. elements in the MIDDLE of a larger block of free space. Adding elements 
  21. is fast because there is free space at each end. When it expands to bump 
  22. either end of its free space, it allocates a larger block of memory from 
  23. the heap and copies all its contents into the MIDDLE of the new block. 
  24. Altering things in the middle is slow because the elements must remian 
  25. contiguous, so up to half of the data will need to move.
  26.  
  27.    David
  28.  
  29.  
  30.